package q240_searchMatrix;

public class Solution_1 {
    public static void main(String[] args) {
        Solution_1 s = new Solution_1();
        System.out.println(s.searchMatrix(new int[][]{{-1, 3}}, 3));
    }

    /**
     * 这种解法是通过寻找一个L形状的范围
     * 前两个函数分别找到第一个大于target的行与列
     * 后一个函数则能够找到target左上角的第一个元素
     * 从而确定target所在的行列范围，然后再开始逐个找target
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {

        int[] startMN = SearchFirstIandJ(matrix, target);
        int C = binarySearchFirstC(matrix, target), R = binarySearchFirstR(matrix, target);
        if (C == -1 && R == -1){
            return false;
        }
        for (int i = startMN[0]; i <= C; i++) {
            for (int j = 0; j <= R; j++ ) {
                if (target == matrix[i][j]) {
                    return true;
                }
            }
        }

        for (int i = startMN[1]; i <= R; i++) {
            for (int j = 0; j <= C; j++ ) {
                if (target == matrix[j][i]) {
                    return true;
                }
            }
        }
        return false;
    }

    public int binarySearchFirstC(int[][] matrix, int target) {
        int low = -1, high = matrix.length - 1;
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            if (matrix[mid][0] <= target) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }

    public int binarySearchFirstR(int[][] matrix, int target) {
        int low = -1, high = matrix[0].length - 1;
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            if (matrix[0][mid] <= target) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }

    public int[] SearchFirstIandJ(int[][] matrix, int target) {
        int i = 0, j = 0;
        while (matrix[i][j] < target && i < matrix.length - 1  && j < matrix[0].length - 1) {
            i++;
            j++;
        }
        return new int[]{i,j};
    }
}
